package 数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class L18 {

    public static void main(String[] args) {
        int[] nums = new int[]{1,-2,-5,-4,-3,3,3,5};
        int target = -11;
        List<List<Integer>> lists = fourSum(nums, target);
        for (List<Integer> list : lists) {
            for (Integer i : list) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {

        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            // 跳过和上一个相同的数字
            if(i > 0 && nums[i] == nums[i-1]) continue;
            for (int j = i + 1; j < nums.length; j++) {
                // 跳过和上一个相同的数字
                if(j > i + 1 && nums[j] == nums[j-1]) continue;

                // 双指针
                int l = j + 1, r = nums.length - 1;
                while (l < r) {
                    int temp = nums[i] + nums[j] + nums[l] + nums[r];
                    if (temp == target) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[l]);
                        list.add(nums[r]);
                        lists.add(list);
                        while(l < r && nums[l+1] == nums[l]) ++l;
                        while (l < r && nums[r-1] == nums[r]) --r;
                        ++l;
                        --r;
                    } else if (temp < target) {
                        ++l;
                    } else {
                        --r;
                    }
                }
            }
        }
        return lists;
    }
}
